{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 基础思想，一部分的回退是不必要的\n",
    "- 维护两个指针，一个回退指针，一个匹配指针"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 创建一个回退列表\n",
    "- 当到最后一位时，在构建下一位的失效指针其实是无意义的，因为已经完成了"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 0, 0, 0, 1, 2, 0, 0, 0, 1, 2, 3, 4, 5]"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "def createDfa(pat):\n",
    "    arr = [0 for i in range(0,len(pat))]\n",
    "    # 前进指针\n",
    "    i = 1\n",
    "    # 回退指针\n",
    "    j = 0\n",
    "    for a in range(0,len(pat)-2):\n",
    "        if pat[i] == pat[j]:\n",
    "                j = j + 1\n",
    "                arr[i+1] = j\n",
    "        else:\n",
    "             j = 0\n",
    "        i += 1\n",
    "    return arr\n",
    "createDfa(\"abcabdddabcabc\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 当p大于0的时候，说明出现了可用的回退指针，此时，i就不应该在前进了，这也是此种方式弊病，即可能造成一定的停顿"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "12"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def search(pat,context):\n",
    "    arr = createDfa(pat)\n",
    "    p = 0\n",
    "    i = 0\n",
    "    while(i < len(context) - 1):\n",
    "        if context[i] == pat[p]:\n",
    "            if p == len(pat) -1:\n",
    "                return i - p\n",
    "            else:\n",
    "                p += 1\n",
    "        else:\n",
    "            p = arr[p]\n",
    "            if p > 0:\n",
    "                continue\n",
    "        i += 1\n",
    "    return 0\n",
    "search(\"abcabdddabcabc\",\"sdfsabcabcdfabcabdddabcabcabcbcabc\")"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
